In the field of parallel processing, the synchronization of many processors working on the same task is an important consideration. If not done efficiently, the synchronization task can over-burden the communication network and greatly reduce the effectiveness of parallel processing or add excessive cost.
One synchronization approach discussed widely in the literature is Global Virtual Time (GVT). In this approach, each processing node can be allowed to free-run and can keep track of its own local time and synchronize with the other processors on-demand. With GVT, the method used to synchronize is to request the local time of all processing nodes and to determine the minimal of those times, which is defined as GVT and indicates how far the entire job has progressed. Without GVT, an individual node would have no idea how far the other nodes had progressed and would be swamped with the amount of data it would have to maintain. Through GVT the idea is to make it possible for all the nodes to remain in loose synchronization and to destroy all old data (which is time-stamped) at times less than GVT.
It is important to handle synchronization techniques, such as GVT, efficiently in parallel systems because they can add a large overhead to parallel operations and negate the effect of the parallelism. This disclosure presents a new and extremely rapid method of synchronizing by using GVT involving all nodes simultaneously in a single operation which occurs over the normal multi-stage interconnection network.